package dfs;

import java.util.HashSet;
import java.util.Set;

/**
 * NumberOfIslands 岛屿数量
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode-cn.com/problems/number-of-islands/
 * @date 2021/5/13
 **/
public class NumberOfIslands {

    class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            Set<String> visited = new HashSet<>();
            int count = 0;
            for (int i = 0; i < grid.length; ++i) {
                for (int j = 0; j < grid[0].length; ++j) {
                    if (grid[i][j] == '1' && !visited.contains(i + "-" + j)) {
                        count++;
                        dfs(i, j, grid, visited);
                    }
                }
            }
            return count;
        }

        private void dfs(int i, int j, char[][] grid, Set<String> visited) {
            if (visited.contains(i + "-" + j)) return;
            visited.add(i + "-" + j);
            //向上
            if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                dfs(i - 1, j, grid, visited);
            }
            //向下
            if (i + 1 < grid.length && grid[i + 1][j] == '1') {
                dfs(i + 1, j, grid, visited);
            }
            //向左
            if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                dfs(i, j - 1, grid, visited);
            }
            //向右
            if (j + 1 < grid[0].length && grid[i][j + 1] == '1') {
                dfs(i, j + 1, grid, visited);
            }
        }
    }

}
